'''
https://leetcode.cn/problems/predict-the-winner/description/
'''
from functools import cache
from typing import List


class Solution:
    # 蛮有意思的递归
    def predictTheWinner(self, nums: List[int]) -> bool:
        @cache
        def f(i, j):
            if i == j:
                return nums[i]
            if i == j - 1:
                return max(nums[i], nums[j])
            # 对手也是绝顶聪明，所以我的下步他肯定会让我拿到最少的
            p1 = nums[i] + min(f(i + 2, j), f(i + 1, j - 1))
            p2 = nums[j] + min(f(i + 1, j - 1), f(i, j - 2))
            # 而我最后又要拿最大的
            return max(p1, p2)

        return f(0, len(nums) - 1) >= sum(nums) / 2

    def predictTheWinner2(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [[0] * n for _ in range(n)]
        # 第一维度依赖后边，第二维度依赖前边
        # 普遍位置依赖下2行，左下角，左边2列, 从下往上，从左往右
        # 初始位置：i==j: dp[i][i] = nums[i]
        #         i==j-1 => j = i+1: dp[i][i+1] = max(nums[i], nums[j])
        # i <= j即只关心上三角
        # 第n-1行，n-2行，0，1列怎么填呢？
        #       最后两列可以根据初始已经填了，前两列也是，所以ok
        dp[-1][-1] = nums[-1]
        for i in range(n - 1):
            dp[i][i] = nums[i]
            dp[i][i + 1] = max(nums[i], nums[i + 1])
        for i in range(n - 3, -1, -1):
            for j in range(i + 2, n):
                p1 = nums[i] + min(dp[i + 2][j], dp[i + 1][j - 1])
                p2 = nums[j] + min(dp[i + 1][j - 1], dp[i][j - 2])
                dp[i][j] = max(p1, p2)
        return dp[0][n - 1] >= sum(nums) / 2
